home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / gfx / 3d / irit50src.lha / irit5 / cagd_lib / afd_cube.c next >
Encoding:
C/C++ Source or Header  |  1995-01-06  |  12.7 KB  |  307 lines
  1. /******************************************************************************
  2. * AFD_Cube.c - Cubic Adaptive forward Differencing code.              *
  3. *                                          *
  4. * This file's code is based on the following cubic polynomial basis function  *
  5. *                                          *
  6. *              C2  2    C3  3                          *
  7. * C(t) = C0 + C1 t + --- t  + --- t    ,   Ci are the coefficients.          *
  8. *              2           3                          *
  9. *                                          *
  10. * For more, see:                                  *
  11. *                                          *
  12. * 1. S. Chang, M. Shantz and R.Rocchetti. Rendering Cubic Curves and          *
  13. *    Surfaces with Integer Adaptive Forward Differencing. Computer Graphics,  *
  14. *    Vol. 23, Num. 3, pp. 157-166, Siggraph Jul. 1989.                  *
  15. * 2. M. Shantz and S. L. Lien. Shading Bicubic Patches. Computer Graphics,    *
  16. *    Vol. 21, Num. 4, pp. 189-196, Siggraph Jul. 1987.                  *
  17. * 3. M. Shantz and S. Chang. Rendering Trimmed NURBS with Adaptive Forward    *
  18. *    Differencing. Computer Graphics, Vol. 22, Num. 4, pp. 189-198,          *
  19. *    Siggraph Aug. 1988.                              *
  20. *******************************************************************************
  21. * Written by Gershon Elber, Jan. 93.                          *
  22. ******************************************************************************/
  23.  
  24. #include <ctype.h>
  25. #include <stdio.h>
  26. #include <string.h>
  27. #include "cagd_loc.h"
  28.  
  29. /*****************************************************************************
  30. * DESCRIPTION:                                                               M
  31. *   Given four coefficents of a cubic Bezier curve, computes the four         M
  32. * coefficients of the cubic afd basis functions, in place.             M
  33. *                                                                            *
  34. * PARAMETERS:                                                                M
  35. *   Coef:    Converts, in place, cubic Bezier Coef to AFD Coef.              M
  36. *                                                                            *
  37. * RETURN VALUE:                                                              M
  38. *   void                                                                     M
  39. *                                                                            M
  40. * KEYWORDS:                                                                  M
  41. *   AfdCnvrtCubicBzrToAfd, forward differencing                              M
  42. *****************************************************************************/
  43. void AfdCnvrtCubicBzrToAfd(CagdRType Coef[4])
  44. {
  45.     CagdRType AfdCoef[4];
  46.  
  47.     AfdCoef[0] = Coef[0];
  48.     AfdCoef[1] = Coef[3] - Coef[0];
  49.     AfdCoef[2] = 6.0 * Coef[3] - 12.0 * Coef[2] + 6.0 * Coef[1];
  50.     AfdCoef[3] = 6.0 * Coef[3] - 18.0 * Coef[2] + 18.0 * Coef[1] - 6.0 * Coef[0];
  51.     CAGD_GEN_COPY(Coef, AfdCoef, sizeof(CagdRType) * 4);
  52. }
  53.  
  54. /*****************************************************************************
  55. * DESCRIPTION:                                                               M
  56. *   Given four coefficents of a cubic afd polynomial, apply the L ( half the M
  57. * step size ) n times to them, in place.                     M
  58. *   We basically precomputed L^n and apply it here once. Every instance of L M
  59. * half the domain and so L^n divides the domain by 2^n.                 M
  60. *                                                                            *
  61. * PARAMETERS:                                                                M
  62. *   Coef:       Four coefficients of the AFD basis functions.                M
  63. *   n:          How many times to compute the L transform.                   M
  64. *                                                                            *
  65. * RETURN VALUE:                                                              M
  66. *   void                                                                     M
  67. *                                                                            M
  68. * KEYWORDS:                                                                  M
  69. *   AfdApplyLn, forward differencing                                         M
  70. *****************************************************************************/
  71. void AfdApplyLn(CagdRType Coef[4], int n)
  72. {
  73.     CagdRType AfdCoef[4];
  74.  
  75.     switch (n) {
  76.     case 1:
  77.         AfdCoef[0] = Coef[0];
  78.         AfdCoef[1] = Coef[1] / 2.0 - Coef[2] / 8.0 + Coef[3] / 16.0;
  79.         AfdCoef[2] = Coef[2] / 4.0 - Coef[3] / 8.0;
  80.         AfdCoef[3] = Coef[3];
  81.         break;
  82.     case 2:
  83.         AfdCoef[0] = Coef[0];
  84.         AfdCoef[1] = Coef[1] / 4.0 - Coef[2] * 3.0 / 32.0 +
  85.                         Coef[3] * 7.0 / 128.0;
  86.         AfdCoef[2] = Coef[2] / 16.0 - Coef[3] * 3.0 / 64.0;
  87.         AfdCoef[3] = Coef[3] / 64.0;
  88.         break;
  89.     case 3:
  90.         AfdCoef[0] = Coef[0];
  91.         AfdCoef[1] = Coef[1] / 8.0 - Coef[2] * 7.0 / 128.0 +
  92.                         Coef[3] * 35.0 / 1024.0;
  93.         AfdCoef[2] = Coef[2] / 64 - Coef[3] * 7.0 / 512.0;
  94.         AfdCoef[3] = Coef[3] / 512.0;
  95.         break;
  96.     case 4:
  97.         AfdCoef[0] = Coef[0];
  98.         AfdCoef[1] = Coef[1] / 16.0 - Coef[2] * 15.0 / 512.0 +
  99.                         Coef[3] * 155.0 / 8192.0;
  100.         AfdCoef[2] = Coef[2] / 256 - Coef[3] * 15.0 / 4096.0;
  101.         AfdCoef[3] = Coef[3] / 4096.0;
  102.         break;
  103.     case 5:
  104.         AfdCoef[0] = Coef[0];
  105.         AfdCoef[1] = Coef[1] / 32.0 - Coef[2] * 31.0 / 2048.0 +
  106.                         Coef[3] * 651.0 / 65536.0;
  107.         AfdCoef[2] = Coef[2] / 1024 - Coef[3] * 31.0 / 32768.0;
  108.         AfdCoef[3] = Coef[3] / 262144.0;
  109.         break;
  110.     case 6:
  111.         AfdCoef[0] = Coef[0];
  112.         AfdCoef[1] = Coef[1] / 64.0 - Coef[2] * 63.0 / 8192.0 +
  113.                         Coef[3] * 2667.0 / 524288.0;
  114.         AfdCoef[2] = Coef[2] / 4096.0 - Coef[3] * 63.0 / 262144.0;
  115.         AfdCoef[3] = Coef[3] / 262144.0;
  116.         break;
  117.     case 7:
  118.         AfdCoef[0] = Coef[0];
  119.         AfdCoef[1] = Coef[1] / 128.0 - Coef[2] * 127.0 / 32768.0 +
  120.                         Coef[3] * 10795.0 / 4194304.0;
  121.         AfdCoef[2] = Coef[2] / 16384.0 - Coef[3] * 127.0 / 2097152.0;
  122.         AfdCoef[3] = Coef[3] / 2097152.0;
  123.         break;
  124.     case 8:
  125.         AfdCoef[0] = Coef[0];
  126.         AfdCoef[1] = Coef[1] / 256.0 - Coef[2] * 255.0 / 131072.0 +
  127.                         Coef[3] * 43435.0 / 33554432.0;
  128.         AfdCoef[2] = Coef[2] / 65536.0 - Coef[3] * 255.0 / 16777216.0;
  129.         AfdCoef[3] = Coef[3] / 16777216.0;
  130.         break;
  131.     case 9:
  132.         AfdCoef[0] = Coef[0];
  133.         AfdCoef[1] = Coef[1] / 512.0 - Coef[2] * 511.0 / 524288.0 +
  134.                     Coef[3] * 174251.0 / 268435456.0;
  135.         AfdCoef[2] = Coef[2] / 262144.0 - Coef[3] * 511.0 / 134217728.0;
  136.         AfdCoef[3] = Coef[3] / 134217728.0;
  137.         break;
  138.     case 10:
  139.         AfdCoef[0] = Coef[0];
  140.         AfdCoef[1] = Coef[1] / 1024.0 - Coef[2] * 1023.0 / 2097152.0 +
  141.                     Coef[3] * 698027.0 / 2147483648.0;
  142.         AfdCoef[2] = Coef[2] / 1048576.0 - Coef[3] * 1023.0 / 1073741824.0;
  143.         AfdCoef[3] = Coef[3] / 1073741824.0;
  144.         break;
  145.     default:
  146.         CAGD_FATAL_ERROR(CAGD_ERR_OUT_OF_RANGE);
  147.         return;
  148.     }
  149.     CAGD_GEN_COPY(Coef, AfdCoef, sizeof(CagdRType) * 4);
  150. }
  151.  
  152. /*****************************************************************************
  153. * DESCRIPTION:                                                               M
  154. *   Given four coefficents of a cubic afd polynomial, apply the E ( step     M
  155. * 1 ) in place.                                     M
  156. *                                                                            *
  157. * PARAMETERS:                                                                M
  158. *   Coef:       Four coefficients of the AFD basis functions.                M
  159. *                                                                            *
  160. * RETURN VALUE:                                                              M
  161. *   void                                                                     M
  162. *                                                                            *
  163. * KEYWORDS:                                                                  M
  164. *   AfdApplyEStep, forward differencing                                      M
  165. *****************************************************************************/
  166. void AfdApplyEStep(CagdRType Coef[4])
  167. {
  168.     Coef[0] += Coef[1];
  169.     Coef[1] += Coef[2];
  170.     Coef[2] += Coef[3];
  171. }
  172.  
  173. /*****************************************************************************
  174. * DESCRIPTION:                                                               M
  175. *   Given four coefficents of a cubic Bezier curve, computes the four         M
  176. * coefficients of the cubic afd basis functions and step along them to       M
  177. * create a piecewise polynomial approximating the curve.             M
  178. *   If NonAdaptive is TRUE then 2^Log2Step constant steps are taken,         M
  179. * creating 2^Log2Step + 1 points along the curve.                 M
  180. *   Otherwise the full blown adaptive algorithm is used.             M
  181. *                                                                            *
  182. * PARAMETERS:                                                                M
  183. *   Coef:          Four coefficients of a cubic Bezier curve.                M
  184. *   Poly:          Where to put the polyline computed.                       M
  185. *   Log2Step:      How many steps to take (2 to the power of this).          M
  186. *   NonAdaptive:   if TRUE, ignore the adaptive option.                      M
  187. *                                                                            *
  188. * RETURN VALUE:                                                              M
  189. *   void                                                                     M
  190. *                                                                            *
  191. * KEYWORDS:                                                                  M
  192. *   AfdComputePolyline, forward differencing                                 M
  193. *****************************************************************************/
  194. void AfdComputePolyline(CagdRType Coef[4],
  195.             CagdRType *Poly,
  196.             int Log2Step,
  197.             CagdBType NonAdaptive)
  198. {
  199.     int i;
  200.     int n = 1 << Log2Step;
  201.  
  202.     AfdCnvrtCubicBzrToAfd(Coef);
  203.     AfdApplyLn(Coef, Log2Step);
  204.  
  205.     if (NonAdaptive) {
  206.     for (i = 0; i <= n; i++) {
  207.         Poly[i] = Coef[0];
  208.         AfdApplyEStep(Coef);
  209.     }
  210.     }
  211.     else
  212.     {
  213.     CAGD_FATAL_ERROR(CAGD_ERR_AFD_NO_SUPPORT);
  214.     }
  215. }
  216.  
  217. /*****************************************************************************
  218. * DESCRIPTION:                                                               M
  219. *   Samples the curves at FineNess location equally spaced in the Bezier     M
  220. * parametric domain [0..1]. If Cache is enabled, and FineNess is power of    M
  221. * two, upto or equal to CacheFineNess, the cache is used, otherwise the      M
  222. * points are evaluated manually for each of the samples.             M
  223. *   Data is saved at the Points array of vectors (according to Curve PType), M
  224. * each vector is assumed to be allocated for FineNess CagdRType points.         M
  225. * Bezier curve must be cubic.                             M
  226. *                                                                            *
  227. * PARAMETERS:                                                                M
  228. *   Crv:         A cubic Bezier curve to piecewuise linear sample using AFD. M
  229. *   FineNess:    Of samples.                                                 M
  230. *   Points:      Whre to put the piecewise linear approximation.             M
  231. *                                                                            *
  232. * RETURN VALUE:                                                              M
  233. *   void                                                                     M
  234. *                                                                            *
  235. * KEYWORDS:                                                                  M
  236. *   AfdBzrCrvEvalToPolyline, forward differencing                            M
  237. *****************************************************************************/
  238. void AfdBzrCrvEvalToPolyline(CagdCrvStruct *Crv,
  239.                  int FineNess,
  240.                  CagdRType *Points[])
  241. {
  242.     CagdBType
  243.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  244.     int i, j,
  245.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  246.     CagdRType
  247.     **CtlPoints = Crv -> Points;
  248.  
  249.     if (Crv -> Order != 4)
  250.     CAGD_FATAL_ERROR(CAGD_ERR_CUBIC_EXPECTED);
  251.  
  252.     for (i = IsNotRational; i <= MaxCoord; i++) {
  253.     CagdRType Coef[4];
  254.  
  255.     for (j = 0; j < 4; j++)
  256.         Coef[j] = CtlPoints[i][j];
  257.  
  258.     AfdComputePolyline(Coef, Points[j], FineNess, TRUE);
  259.     }
  260. }
  261.  
  262. #ifdef DEBUG_AFD
  263.  
  264. /* If this section is defined, this file can be compiled stand alone. */
  265.  
  266. void CagdFatalError(CagdFatalErrorType ErrID)
  267. {
  268. }
  269.  
  270. void main(int argc, char **argv)
  271. {
  272.     CagdRType
  273.     Poly[1025],
  274.     Coef[4] = { 0.0, 1.0, 2.0, 3.0 };
  275.     int i,
  276.     Log2Step = 6;
  277.  
  278.     while (argc >= 2) {
  279.     if (argc >= 2 && strcmp( argv[1], "-s" ) == 0) {
  280.         Log2Step = atoi( argv[2] );
  281.         argc -= 2;
  282.         argv += 2;
  283.     }
  284.     else if (argc >= 2 && strcmp( argv[1], "-c" ) == 0) {
  285.         Coef[0] = atof(argv[2]);
  286.         Coef[1] = atof(argv[3]);
  287.         Coef[2] = atof(argv[4]);
  288.         Coef[3] = atof(argv[5]);
  289.         argc -= 5;
  290.         argv += 5;
  291.     }
  292.     else {
  293.         fprintf(stderr, "Wrong command line");
  294.         exit(1);
  295.     }
  296.     }
  297.  
  298.     printf("Steps = %d, Coef = %lf %lf %lf %lf\n",
  299.        Log2Step, Coef[0], Coef[1], Coef[2], Coef[3]);
  300.  
  301.     AfdComputePolyline(Coef, Poly, Log2Step, TRUE);
  302.     for (i = 0; i <= (1 << Log2Step); i++)
  303.     printf("%d = %lg\n", i, (double) Poly[i]);
  304. }
  305.  
  306. #endif /* DEBUG_AFD */
  307.